//1456.定长子串中元音的最大数目

//给你字符串s和整数k
//请返回字符串s中长度为k的单个子字符串中可能包含的最大元音字母数
//英文中的元音字母为（a,e,i,o,u）

//class Solution {
//public:
//    int maxVowels(string s, int k) {
//        int ans{}, vowel{};
//        for (int i{}; i < s.length(); i++) {
//            // 1. 进入窗口
//            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
//                vowel++;
//            }
//            if (i < k - 1) { // 窗口大小不足 k
//                continue;
//            }
//            // 2. 更新答案
//            ans = max(ans, vowel);
//            // 3. 离开窗口，为下一个循环做准备
//            char out = s[i - k + 1];
//            if (out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {
//                vowel--;
//            }
//        }
//        return ans;
//    }
//};

//643.子数组最大平均数 I

//给你一个由n个元素组成的整数数组nums和一个整数k
//请你找出平均数最大且长度为k的连续子数组，并输出该最大平均数
//任何误差小1E-5的答案都将被视为正确答案

//class Solution {
//public:
//    double findMaxAverage(vector<int>& nums, int k) {
//        int num{}, n = nums.size(), sum{};
//        double res = INT_MIN; //可能为负
//        for (int i{}; i < n; i++) {
//            sum += nums[i];
//            num++;
//            if (num == k) {//判断窗口是否达标
//                res = max(res, (double)sum / k);
//                //重置窗口
//                sum -= nums[i - k + 1];
//                num--;
//            }
//        }
//        return res;
//    }
//};

//1343.大小为K且平均值大于等于阈值的子数组数目

//给你一个整数数组arr和两个整数k和threshold 
//请你返回长度为k且平均值大于等于threshold的子数组数目

//class Solution {
//public:
//    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
//        int ans{};
//        int s{}; // 维护窗口元素和
//        for (int i{}; i < arr.size(); i++) {
//            // 1. 进入窗口
//            s += arr[i];
//            if (i < k - 1) { // 窗口大小不足 k
//                continue;
//            }
//            // 2. 更新答案
//            ans += s >= k * threshold;
//            // 3. 离开窗口
//            s -= arr[i - k + 1];
//        }
//        return ans;
//    }
//};

//2090.半径为k的子数组平均值 

//给你一个下标从0开始的数组nums，数组中有n个整数，另给你一个整数k
//半径为k的子数组平均值 是指：nums中一个以下标i为中心且半径为k的子数组中所有元素的平均值，即下标在i-k和i+k范围（含i-k和i+k）内所有元素的平均值。如果在下标i前或后不足k个元素，那么半径为k的子数组平均值是-1
//构建并返回一个长度为n的数组avgs，其中avgs[i]是以下标i为中心的子数组的 半径为 k 的子数组平均值
//x个元素的平均值是x个元素相加之和除以x，此时使用截断式 整数除法，即需要去掉结果的小数部分
//例如，四个元素2、3、1和5的平均值是(2+3+1+5)/4=11/4=2.75，截断后得到2

//class Solution {
//public:
//    vector<int> getAverages(vector<int>& nums, int k) {
//        int n = nums.size();
//        vector<int> res(n, -1);
//        long long s{};
//
//        for (int i{}; i < n; i++) {
//            s += nums[i];
//            if (i < k * 2) {
//                continue;
//            }
//            res[i - k] = s / (k * 2 + 1);
//            s -= nums[i - k * 2];
//        }
//
//        return res;
//    }
//};

//2379.得到K个黑块的最少涂色次数

//给你一个长度为n下标从0开始的字符串blocks，blocks[i]要么是'W'要么是'B'，表示第i块的颜色。字符'W'和'B'分别表示白色和黑色
//给你一个整数k，表示想要连续黑色块的数目
//每一次操作中，你可以选择一个白色块将它涂成黑色块
//请你返回至少出现一次连续k个黑色块的最少操作次数

//class Solution {
//public:
//    int minimumRecolors(string blocks, int k) {
//        int cnt_w{};
//        for (int i{}; i < k; i++) {
//            cnt_w += blocks[i] & 1; //ASCII码上‘W’最低位值为1，‘B’为0
//        }
//
//        int ans = cnt_w;
//        for (int i = k; i < blocks.size(); i++) {
//            cnt_w += (blocks[i] & 1) - (blocks[i - k] & 1);
//            ans = min(ans, cnt_w);
//        }
//
//        return ans;
//    }
//};

//2841.几乎唯一子数组的最大和

//给你一个整数数组nums和两个正整数 m 和 k 
//请你返回nums中长度为k的几乎唯一子数组的最大和，如果不存在几乎唯一子数组，请你返回0
//如果nums的一个子数组有至少m个互不相同的元素，我们称它是几乎唯一子数组
//子数组指的是一个数组中一段连续非空的元素序列

//class Solution {
//public:
//    long long maxSum(vector<int>& nums, int m, int k) {
//        long long ans{}, s{};
//        unordered_map<int, int> cnt;
//        for (int i{}; i < nums.size(); i++) {
//            s += nums[i];
//            cnt[nums[i]]++;
//
//            int left = i - k + 1;
//            if (left < 0) {
//                continue;
//            }
//
//            if (cnt.size() >= m) {
//                ans = max(ans, s);
//            }
//
//            int out = nums[left];
//            s -= out;
//            if (--cnt[out] == 0) {
//                cnt.erase(out);
//            }
//        }
//
//        return ans;
//    }
//};

//2461.长度为K子数组中的最大和

//给你一个整数数组nums和一个整数k。请你从nums中满足下述条件的全部子数组中找出最大子数组和：
//子数组的长度是k，且子数组中的所有元素各不相同
//返回满足题面要求的最大子数组和，如果不存在子数组满足这些条件，返回 0
//子数组 是数组中一段连续非空的元素序列

//class Solution {
//public:
//    long long maximumSubarraySum(vector<int>& nums, int k) {
//        long long ans = 0, s = 0;
//        unordered_map<int, int> cnt;
//        for (int i = 0; i < nums.size(); i++) {
//            s += nums[i];
//            cnt[nums[i]]++;
//
//            int left = i - k + 1;
//            if (left < 0) {
//                continue;
//            }
//
//            if (cnt.size() == k) {
//                ans = max(ans, s);
//            }
//
//            int out = nums[left];
//            s -= out;
//            if (--cnt[out] == 0) {
//                cnt.erase(out);
//            }
//        }
//
//        return ans;
//    }
//};

//1423.可获得的最大点数

//几张卡牌排成一行，每张卡牌都有一个对应的点数。点数由整数数组cardPoints给出
//每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿k张卡牌
//你的点数就是你拿到手中的所有卡牌的点数之和
//给你一个整数数组cardPoints和整数k，请你返回可以获得的最大点数

//class Solution {
//public:
//    int maxScore(vector<int>& cardPoints, int k) {
//        int s = reduce(cardPoints.begin(), cardPoints.begin() + k);
//        int ans = s;
// 
//        for (int i = 1; i <= k; i++) {
//            s += cardPoints[cardPoints.size() - i] - cardPoints[k - i];
//            ans = max(ans, s);
//        }
// 
//        return ans;
//    }
//};

//1052.爱生气的书店老板

//有一个书店老板，他的书店开了n分钟。每分钟都有一些顾客进入这家商店。给定一个长度为n的整数数组customers，其中customers[i]是在第i分钟开始时进入商店的顾客数量，所有这些顾客在第i分钟结束后离开
//在某些分钟内，书店老板会生气。如果书店老板在第i分钟生气，那么grumpy[i]=1，否则grumpy[i] = 0
//当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的
//书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续minutes分钟不生气，但却只能使用一次
//请你返回这一天营业下来，最多有多少客户能够感到满意

//class Solution {
//public:
//    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
//        int s[2]{}, max_s1 = 0;
//        for (int i = 0; i < customers.size(); i++) {
//            s[grumpy[i]] += customers[i];
//            if (i < minutes - 1) {
//                continue;
//            }
//            max_s1 = max(max_s1, s[1]);
//            // 窗口最左边元素离开窗口
//            s[1] -= grumpy[i - minutes + 1] ? customers[i - minutes + 1] : 0;
//        }
//
//        return s[0] + max_s1;
//    }
//};


//1652.拆炸弹

//你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为n的循环数组code以及一个密钥k。
//为了获得正确的密码，你需要替换掉每一个数字。所有数字会同时被替换。
//如果k>0 ，将第i个数字用接下来k个数字之和替换。
//如果k<0 ，将第i个数字用之前k个数字之和替换。
//如果k==0 ，将第i个数字用0替换。
//由于code是循环的，code[n-1]下一个元素是code[0]，且code[0]前一个元素是code[n-1]。
//给你循环数组code和整数密钥k，请你返回解密后的结果来拆除炸弹！

//class Solution {
//public:
//    vector<int> decrypt(vector<int>& code, int k) {
//        int n = code.size();
//        vector<int> ans(n, 0);
//
//        if (!k) {
//            return ans;
//        }
//
//        int r = k > 0 ? k + 1 : n; // 第一个窗口的右开端点
//        k = abs(k);
//        int s = reduce(code.begin() + r - k, code.begin() + r); // ans[0]
//        for (int i = 0; i < n; i++) {
//            ans[i] = s;
//            s += code[r % n] - code[(r - k) % n];
//            r++;
//        }
//
//        return ans;
//    }
//};

//3439.重新安排会议得到最多空余时间 I

//给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。
//同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为[startTime[i], endTime[i]] 。
//你可以重新安排 至多 k 个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。
//移动前后所有会议之间的 相对 顺序需要保持不变，而且会议时间也需要保持互不重叠。
//请你返回重新安排会议以后，可以得到的 最大 空余时间。
//注意，会议 不能 安排到整个活动的时间以外。

//class Solution {
//public:
//    int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
//        int n = startTime.size(), res = 0, t = 0;
//        for (int i = 0; i < n; i++) {
//            t += endTime[i] - startTime[i];
//            int left = i <= k - 1 ? 0 : endTime[i - k];
//            int right = i == n - 1 ? eventTime : startTime[i + 1];
//            res = max(res, right - left - t);
//            if (i >= k - 1) {
//                t -= endTime[i - k + 1] - startTime[i - k + 1];
//            }
//        }
//        return res;
//    }
//};

//2134.最少交换次数来组合所有的 1 II

//交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。
//环形 数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。
//给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。

//class Solution {
//public:
//    int minSwaps(vector<int>& nums) {
//        int n = nums.size();
//        int cnt = accumulate(nums.begin(), nums.end(), 0);
//        if (cnt == 0) {
//            return 0;
//        }
//
//        int cur{};
//        for (int i{}; i < cnt; ++i) {
//            cur += (1 - nums[i]);
//        }
//        int ans = cur;
//        for (int i = 1; i < n; ++i) {
//            if (nums[i - 1] == 0) {
//                --cur;
//            }
//            if (nums[(i + cnt - 1) % n] == 0) {
//                ++cur;
//            }
//            ans = min(ans, cur);
//        }
//        return ans;
//    }
//};

//1297.子串的最大出现次数

//给你一个字符串s，请你返回满足以下条件且出现次数最大的任意子串的出现次数：
//子串中不同字母的数目必须小于等于 maxLetters
//子串的长度必须大于等于minSize且小于等于maxSize

//class Solution {
//public:
//    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
//        int ans{};
//        unordered_map<char, int>mp;//记录字符种类和数目
//        unordered_map<string, int>times;//记录不同字符传
//
//        string str;
//        for (int i{}; i < s.length(); i++)
//        {
//            //入
//            mp[s[i]]++;
//            str += s[i];
//
//            int left = i - minSize + 1;//记录左边界，这里滑块长度只取较小的
//            if (left < 0) continue;
//            times[str]++;
//
//            if (mp.size() <= maxLetters)//不同字符个数小于maxLetters才能更新
//                ans = max(ans, times[str]);
//
//            str.erase(str.begin());//出
//            if (--mp[s[left]] == 0) mp.erase(s[left++]);//最后要把左边界左移一位用于更新
//
//        }
//        return ans;
//    }
//};

//2653.滑动子数组的美丽值

//给你一个长度为n的整数数组nums，请你求出每个长度为k的子数组的美丽值
//一个子数组的美丽值定义为：如果子数组中第x小整数是负数 ，那么美丽值为第x小的数，否则美丽值为0
//请你返回一个包含n - k + 1个整数的数组，依次表示数组中从第一个下标开始，每个长度为 k 的子数组的美丽值
//子数组指的是数组中一段连续非空的元素序列。

//class Solution {
//public:
//    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
//        const int BIAS = 50;
//        int cnt[BIAS * 2 + 1]{};
//        for (int i{}; i < k - 1; i++) { // 先往窗口内添加 k-1 个数
//            cnt[nums[i] + BIAS]++;
//        }
//
//        int n = nums.size();
//        vector<int> ans(n - k + 1);
//        for (int i = k - 1; i < n; i++) {
//            cnt[nums[i] + BIAS]++; // 进入窗口（保证窗口有恰好 k 个数）
//            int left = x;
//            for (int j{}; j < BIAS; j++) { // 暴力枚举负数范围 [-50,-1]
//                left -= cnt[j];
//                if (left <= 0) { // 找到美丽值
//                    ans[i - k + 1] = j - BIAS;
//                    break;
//                }
//            }
//            cnt[nums[i - k + 1] + BIAS]--; // 离开窗口
//        }
//
//        return ans;
//    }
//};

//1888.使二进制字符串字符交替的最少反转次数

//给你一个二进制字符串s。你可以按任意顺序执行以下两种操作任意次：
//类型1：删除 字符串s的第一个字符并将它添加到字符串结尾。
//类型2：选择 字符串s中任意一个字符并将该字符反转，也就是如果值为'0'，则反转得到'1'，反之亦然。
//请你返回使s变成交替字符串的前提下，类型2的最少操作次数
//我们称一个字符串是交替的，需要满足任意相邻字符都不同。
//比方说，字符串"010"和"1010"都是交替的，但是字符串"0100"不是。

//class Solution {
//public:
//    int minFlips(string s) {
//        int n = s.size(), ans = n, cnt = 0;
//        for (int i = 0; i < n * 2 - 1; i++) {
//            if (s[i % n] % 2 != i % 2) {
//                cnt++;
//            }
//            int left = i - n + 1;
//            if (left < 0) {
//                continue;
//            }
//            ans = min({ ans, cnt, n - cnt });
//            if (s[left] % 2 != left % 2) {
//                cnt--;
//            }
//        }
//
//        return ans;
//    }
//};

//567.字符串的排列

//给你两个字符串s1和s2，写一个函数来判断s2是否包含s1的排列。如果是，返回true；否则，返回false。
//换句话说，s1的排列之一是s2的子串

//class Solution {
//public:
//    bool checkInclusion(string s1, string s2) {
//        // 在s2中维护一个长度为s1长度的窗口 窗口内有所有s1的字符 即可返回true
//        multiset<char> pt, t;
//        for (auto& ch : s1)pt.insert(ch);
//        int k = s1.size(), n = s2.size();
//        for (int i{}; i < n; i++) {
//            t.insert(s2[i]);
//            if (i < k - 1)continue;
//            if (pt == t) return true;
//            auto it = t.find(s2[i - k + 1]);
//            t.erase(it);
//        }
//
//        return false;
//    }
//};

//438.找到字符串中所有字母异位词

//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p) {
//        vector<int> ans;
//        array<int, 26> cnt_p{};
//        array<int, 26> cnt_s{};
//
//        for (char c : p) {
//            cnt_p[c - 'a']++;
//        }
//        for (int right = 0; right < s.length(); right++) {
//            cnt_s[s[right] - 'a']++;
//            int left = right - p.length() + 1;
//            if (left < 0) {
//                continue;
//            }
//            if (cnt_s == cnt_p) {
//                ans.push_back(left);
//            }
//            cnt_s[s[left] - 'a']--;
//        }
//
//        return ans;
//    }
//};

//30.串联所有单词的子串

//给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
//s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
//例如，如果 words = ["ab", "cd", "ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
//返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

//class Solution {
//public:
//    vector<int> findSubstring(string s, vector<string>& words) {
//        int word_len = words[0].size(); // 一个单词的长度
//        int window_len = word_len * words.size(); // 所有单词的总长度，即窗口大小
//
//        // 目标：窗口中的单词出现次数必须与 target_cnt 完全一致
//        unordered_map<string, int> target_cnt;
//        for (auto& w : words) {
//            target_cnt[w]++;
//        }
//
//        vector<int> ans;
//        // 枚举窗口起点，做 word_len 次滑动窗口
//        for (int start = 0; start < word_len; start++) {
//            unordered_map<string, int> cnt;
//            int overload = 0;
//            // 枚举窗口最后一个单词的右端点+1
//            for (int right = start + word_len; right <= s.size(); right += word_len) {
//                // 1. in_word 进入窗口
//                string in_word = s.substr(right - word_len, word_len);
//                // 下面 cnt[in_word]++ 后，in_word 的出现次数过多
//                if (cnt[in_word] == target_cnt[in_word]) {
//                    overload++;
//                }
//                cnt[in_word]++;
//
//                int left = right - window_len; // 窗口第一个单词的左端点
//                if (left < 0) { // 窗口大小不足 window_len
//                    continue;
//                }
//
//                // 2. 更新答案
//                // 如果没有超出 target_cnt 的单词，那么也不会有少于 target_cnt 的单词
//                if (overload == 0) {
//                    ans.push_back(left);
//                }
//
//                // 3. 窗口最左边的单词 out_word 离开窗口，为下一轮循环做准备
//                string out_word = s.substr(left, word_len);
//                cnt[out_word]--;
//                if (cnt[out_word] == target_cnt[out_word]) {
//                    overload--;
//                }
//            }
//        }
//
//        return ans;
//    }
//};

//2156.查找给定哈希值的子串

//给定整数 p 和 m ，一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算：
//hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k - 1]) * pk - 1) mod m.
//其中 val(s[i]) 表示 s[i] 在字母表中的下标，从 val('a') = 1 到 val('z') = 26 。
//给你一个字符串 s 和整数 power，modulo，k 和 hashValue 。请你返回 s 中 第一个 长度为 k 的 子串 sub ，满足 hash(sub, power, modulo) == hashValue 。
//测试数据保证一定 存在 至少一个这样的子串。
//子串 定义为一个字符串中连续非空字符组成的序列

//class Solution {
//public:
//    string subStrHash(string s, int power, int mod, int k, int hashValue) {
//        int n = s.length();
//        // 用秦九韶算法计算 s[n-k:] 的哈希值，同时计算 pk=power^k
//        long long hash = 0, pk = 1;
//        for (int i = n - 1; i >= n - k; i--) {
//            hash = (hash * power + (s[i] & 31)) % mod;
//            pk = pk * power % mod;
//        }
//        int ans = hash == hashValue ? n - k : 0;
//        // 向左滑窗
//        for (int i = n - k - 1; i >= 0; i--) {
//            // 计算新的哈希值，注意 +mod 防止计算出负数
//            hash = (hash * power + (s[i] & 31) - pk * (s[i + k] & 31) % mod + mod) % mod;
//            if (hash == hashValue) {
//                ans = i;
//            }
//        }
//
//        return s.substr(ans, k);
//    }
//};

//2953.统计完全子字符串

//给你一个字符串 word 和一个整数 k 。
//如果 word 的一个子字符串 s 满足以下条件，我们称它是 完全字符串：
//s 中每个字符 恰好 出现 k 次。
//相邻字符在字母表中的顺序 至多 相差 2 。也就是说，s 中两个相邻字符 c1 和 c2 ，它们在字母表中的位置相差 至多 为 2 。
//请你返回 word 中 完全 子字符串的数目。
//子字符串 指的是一个字符串中一段连续 非空 的字符序列。

//class Solution {
//    int f(string_view s, int k) {
//        int res = 0;
//        for (int m = 1; m <= 26 && k * m <= s.length(); m++) {
//            int cnt[26]{};
//            auto check = [&]() {
//                for (int i = 0; i < 26; i++) {
//                    if (cnt[i] && cnt[i] != k) {
//                        return;
//                    }
//                }
//                res++;
//                };
//            for (int right = 0; right < s.length(); right++) {
//                cnt[s[right] - 'a']++;
//                int left = right + 1 - k * m;
//                if (left >= 0) {
//                    check();
//                    cnt[s[left] - 'a']--;
//                }
//            }
//        }
//        return res;
//    }
//
//public:
//    int countCompleteSubstrings(string word, int k) {
//        int n = word.length();
//        int ans = 0;
//        string_view s(word); // string_view 的 substr 没有拷贝
//        for (int i = 0; i < n;) {
//            int st = i;
//            for (i++; i < n && abs(int(word[i]) - int(word[i - 1])) <= 2; i++);
//            ans += f(s.substr(st, i - st), k);
//        }
// 
//        return ans;
//    }
//};

//1016.子串能表示从1到N数字的二进制串做到O(|s|)

//给定一个二进制字符串 s 和一个正整数 n，如果对于[1, n] 范围内的每个整数，其二进制表示都是 s 的 子字符串 ，就返回 true，否则返回 false 。
//子字符串 是字符串中连续的字符序列。

//class Solution {
//public:
//    bool queryString(string s, int n) {
//        for (int i = 1; i <= n; i++) {
//            auto bin = bitset<32>(i).to_string();
//            bin = bin.substr(bin.find('1'));
//            if (s.find(bin) == string::npos)
//                return false;
//        }
//
//        return true;
//    }
//};

//2269.找到一个数字的K美丽值

//一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目：
//子字符串长度为 k 。
//子字符串能整除 num 。
//给你整数 num 和 k ，请你返回 num 的 k 美丽值。
//注意：
//允许有 前缀 0 。
//0 不能整除任何值。
//一个 子字符串 是一个字符串里的连续一段字符序列

//class Solution {
//public:
//    int divisorSubstrings(int num, int k) {
//        string s = to_string(num);
//        int n = s.size();
//        int res = 0;
//        for (int i = 0; i <= n - k; ++i) {
//            int tmp = stoi(s.substr(i, k));
//            if (tmp && num % tmp == 0) {
//                ++res;
//            }
//        }
//
//        return res;
//    }
//};

//1984.学生分数的最小差值

//给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
//从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
//返回可能的 最小差值 。

//class Solution {
//public:
//    int minimumDifference(vector<int>& nums, int k)
//    {
//        sort(nums.begin(), nums.end());
//        int ans = INT_MAX;
//        deque<int> dque;
//        for (int i{}; i < nums.size(); i++)
//        {
//            dque.push_back(nums[i]);
//            if (i < k - 1)
//                continue;
//            auto [min_it, max_it] = std::minmax_element(dque.begin(), dque.end());
//            int div = abs(*max_it - *min_it);
//            ans = min(ans, div);
//            dque.pop_front();
//        }
//
//        return ans;
//    }
//};

//1461.检查一个字符串是否包含所有长度为K的二进制子串

//给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false

//class Solution {
//public:
//    bool hasAllCodes(string s, int k) {
//        if (s.size() < (1 << k) + k - 1) {
//            return false;
//        }
//
//        int num = stoi(s.substr(0, k), nullptr, 2);
//        unordered_set<int> exists = { num };
//
//        for (int i = 1; i + k <= s.size(); ++i) {
//            num = (num - ((s[i - 1] - '0') << (k - 1))) * 2 + (s[i + k - 1] - '0');
//            exists.insert(num);
//        }
//
//        return exists.size() == (1 << k);
//    }
//};

//220.存在重复元素 III

//给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。
//找出满足下述条件的下标对(i, j)：
//i != j,
//abs(i - j) <= indexDiff
//abs(nums[i] - nums[j]) <= valueDiff
//如果存在，返回 true ；否则，返回 false 。

//class Solution {
//public:
//    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
//        int n = nums.size();
//        set<int> rec;
//        for (int i = 0; i < n; i++) {
//            auto iter = rec.lower_bound(max(nums[i], INT_MIN + t) - t);
//            if (iter != rec.end() && *iter <= min(nums[i], INT_MAX - t) + t) {
//                return true;
//            }
//            rec.insert(nums[i]);
//            if (i >= k) {
//                rec.erase(nums[i - k]);
//            }
//        }
//
//        return false;
//    }
//};